package demo.practice.uf;

import java.util.*;

public class P721_1 {

    public static void main(String[] args) {
        P721_1 p721 = new P721_1();
        List<List<String>> accounts = new ArrayList<>();
        accounts.add(new ArrayList<>(Arrays.asList("John", "johnsmith@mail.com", "john_newyork@mail.com")));
        accounts.add(new ArrayList<>(Arrays.asList("John", "johnsmith@mail.com", "john00@mail.com")));
        accounts.add(new ArrayList<>(Arrays.asList("Mary", "mary@mail.com")));
        accounts.add(new ArrayList<>(Arrays.asList("John", "johnnybravo@mail.com")));
        p721.accountsMerge(accounts);
    }

    public List<List<String>> accountsMerge(List<List<String>> accounts) {
        UF uf = new UF();
        for (List<String> account : accounts) {
            String name = account.get(0);
            if (account.size() == 2) {
                uf.add(account.get(1), name);
            } else
                for (int i = 1; i < account.size() - 1; i++) {
                    uf.join(account.get(i), name, account.get(i + 1), name);
                }
        }

        List<List<String>> res = new ArrayList<>();
        for (Map.Entry<String, TreeSet<String>> en : uf.email.entrySet()) {

            List<String> a = new ArrayList<>();
            a.add(uf.names.get(en.getKey()));
            a.addAll(en.getValue());
            res.add(a);

        }
        return res;
    }

    class UF {

        Map<String, String> parent = new HashMap<>();
        public Map<String, TreeSet<String>> email = new HashMap<>();
        public Map<String, String> names = new HashMap<>();

        UF() {
            //啥也不做了
        }

        public String findP(String a) {
            if (a == null)
                //
                throw new RuntimeException("查找元素不为空");
            while (!a.equals(parent.get(a))) {
                String pa = parent.get(a);
                if (pa == null)
                    return null;
                else {
                    a = pa;
                }
            }
            return a;
        }

        public void add(String a, String name) {
            if (a == null)//忽略
                return;

            if (findP(a) != null)
                return;

            init(a, name);
        }


        private void init(String a, String name) {
            parent.put(a, a);
            names.put(a, name);
            TreeSet<String> e = new TreeSet<>((o, o1) -> o.compareTo(o1));
            e.add(a);
            email.put(a, e);
        }

        public void join(String a, String na, String b, String nb) {
            if (a == null || b == null)//忽略合并
                return;
            String pa = findP(a);
            String pb = findP(b);

            if (pa == null) {
                init(a, na);
                join(a, na, b, nb);
                return;
            }

            if (pb == null) {
                init(b, nb);
                join(a, na, b, nb);
                return;
            }

            if (!pa.equals(pb)) {
                parent.put(pb, pa);
                email.get(pa).addAll(email.get(pb));
                email.remove(pb);
            }
        }
    }
}
